/**
 * @program: LeetCode
 * @description: LeetCode : 2550. 猴子碰撞的方法数
 * @author: WXY
 * @create: 2023-01-30 12:48
 * @Version 1.0
 *
 * 所有的 移动方法是2^n  ,只有往同一方向移动才不会碰撞，所以答案是(2^n - 2)
 **/
public class Num2550_monkeyMove {
    public static int monkeyMove1(int n) {
        int MOD = (int) (1e9 + 7);
        int ans = ((1 << n) - 2) % MOD;
        return ans ;
    }
    public static int monkeyMove(int n) {
        int MOD = (int) (1e9 + 7);
        long ans = 1;
        long temp = 2;
        while (n > 0) {
            if (n % 2 == 1) {
                ans = (ans * temp) % MOD;
            }
            temp = (temp * temp) % MOD;
            n = n >> 1;
        }
        return (int) (ans - 2 + MOD) % MOD;
    }

    public static void main(String[] args) {
        int n = 6;
        System.out.println(monkeyMove(n));
    }
}
